package _06_动态规划;

import java.util.Arrays;
import java.util.List;

public class _120_三角形最小路径和 {

    public static int minimumTotal(List<List<Integer>> triangle) {
        int lastSize = triangle.get(triangle.size() - 1).size();
        int[] dp = new int[lastSize];
        // 填充最大值
        Arrays.fill(dp, Integer.MAX_VALUE);
        // dp数据初始化
        dp[0] = triangle.get(0).get(0);
        int size = triangle.size();
        for (int i = 1; i < size; i++) {
            // 拿到当前元素的上一个元素，或者上一个元素的i - 1
            List<Integer> list = triangle.get(i);
            int subSize = list.size();
            int prevEle = -1;
            for (int j = 0; j < subSize; j++) {
                int prev = prevEle;
                prevEle = dp[j];
                // 保存上一次遍历的值
                dp[j] = Math.min(j - 1 < 0 ? Integer.MAX_VALUE : prev, dp[j]) + list.get(j);
            }
        }
        int minPath = Integer.MIN_VALUE;
        for (int j : dp) {
            minPath = Math.min(j, minPath);
        }
        return minPath;
    }

}
